1110. 删点成林【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - DFS

1. 📝 题目描述

• leetcode

给出二叉树的根节点 root，树上每个节点都有一个不同的值。

如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。

返回森林中的每棵树。你可以按任意顺序组织答案。

---

示例 1：

输入：root = [1,2,3,4,5,6,7], to_delete = [3,5]
输出：[[1,2,null,4],[6],[7]]

示例 2：

输入：root = [1,2,4,null,3], to_delete = [3]
输出：[[1,2,4]]

---

提示：

• 树中的节点数最大为 1000。
• 每个节点都有一个介于 1 到 1000 之间的值，且各不相同。
• to_delete.length <= 1000
• to_delete 包含一些从 1 到 1000、各不相同的值。

2. 🎯 s.1 - DFS

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {TreeNode} root
 * @param {number[]} to_delete
 * @return {TreeNode[]}
 */
var delNodes = function (root, to_delete) {
  const delSet = new Set(to_delete)
  const res = []
  function dfs(node, isRoot) {
    if (!node) return null
    const deleted = delSet.has(node.val)
    if (isRoot && !deleted) res.push(node)
    node.left = dfs(node.left, deleted)
    node.right = dfs(node.right, deleted)
    return deleted ? null : node
  }
  dfs(root, true)
  return res
}

• 时间复杂度：$O(n)$，其中 $n$ 是树的节点数
• 空间复杂度：$O(n)$，哈希集合和递归栈的开销

算法思路：

• 将待删除节点存入哈希集合，DFS 遍历树
• 每个节点判断是否被删除：若被删除则其子节点成为新根
• 若当前节点是根且未被删除，则加入结果集